package problems.daily;

/**
 * 1769. 移动所有球到每个盒子所需的最小操作数
 * <p>https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/</p>
 *
 * @author habitplus
 * @since 9:09, 2022/12/2
 */
public class DT1769 {
    public int[] minOperations(String boxes) {
        char[] chs = boxes.toCharArray();
        int n = chs.length;

        int[] ret = new int[n];
        int cnt = 0;
        for (int i = n - 2; i >= 0; --i) {
            // 记录右边 1 的个数
            cnt += chs[i + 1] - '0';
            ret[i] = ret[i + 1] + cnt;
        }

        cnt = 0;
        // 左边累加和
        int leftSum = 0;
        for (int i = 1; i < n; ++i) {
            // 记录左边 1 的个数
            cnt += chs[i - 1] - '0';
            leftSum += cnt;
            ret[i] += leftSum;
        }

        return ret;
    }
}
